package code.lru;

import java.util.*;

public class LRUCache {
    class DLinkedNode {
        private int key;
        private int value;
        private DLinkedNode prev;
        private DLinkedNode next;
        public DLinkedNode() {};
        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        };
    }

    Map<Integer, DLinkedNode> cache = new HashMap<>();

    // 虚拟的头尾节点
    DLinkedNode head;
    DLinkedNode tail;

    int capacity;

    int size;

    public LRUCache(int _capacity) {
        capacity = _capacity;
        size = 0;

        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        DLinkedNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void set(int key, int value) {
        if (!cache.containsKey(key)) {
            DLinkedNode addNode = new DLinkedNode(key, value);
            cache.put(key, addNode);
            addToHead(addNode);
            ++size;
            if (size > capacity) {
                DLinkedNode tailNode = tail.prev;
                removeNode(tailNode);
                cache.remove(tailNode.key);
                --size;
            }
            return;
        }
        DLinkedNode node = cache.get(key);
        moveToHead(node);
        node.value = value;
    }

    public void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void addToHead(DLinkedNode node) {
        node.next = head.next;
        node.prev = head;

        head.next.prev = node;
        head.next = node;

    }

    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    public List<Integer> Print() {
        List<Integer> res = new ArrayList<>();
        DLinkedNode node = head.next;
        while(node != tail) {
            res.add(node.key);
            node = node.next;
        }
        return res;
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(5);
        lru.set(1,1);
        lru.set(2,2);
        lru.set(3,3);
        lru.set(4,4);
        lru.set(5,5);
        System.out.println(lru.Print()); // 5,4,3,2,1
        lru.set(6,6);
        System.out.println(lru.Print()); // 6,5,4,3,2
        int value = lru.get(2);
        System.out.println(value); // 2
        System.out.println(lru.Print()); // 2,6,5,4,3
        lru.set(6,5);
        System.out.println(lru.Print()); // 6,2,5,4,3
    }
}
